Skip to main content

Lagrange Polynomial

Polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset. Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.

Definition

The Lagrange interpolating polynomial for nodes y0,y1,...,yk{y_0, y_1, ..., y_k} is the linear combination:

j=0kyjlj(x)\sum_{j=0}^{k} {y_j*l_j(x)}

Where lj(x)l_j(x) is Langrange basis (polynomial):

lj(x)=mj,m>=0xxmxjxm\mathcal{l_j}(x) = \prod_{m \neq j, m >= 0}\frac{x -x_m}{x_j - x_m}

As mentioned above the interpolating polynomial is unique 1. This characteristic allows uses in cryptography such as: Shamir's secret sharing scheme and KZG polynomial 2 commitments (Kate commitment) [https://en.m.wikipedia.org/wiki/Lagrange_polynomial] 1 *[https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf] 2

Uses

Vector commitment and Verkle Tries

A commitment scheme allows one to commit to a chosen value (or statement) while keeping it hidden to others, with the ability to reveal the committed value later [https://en.m.wikipedia.org/wiki/Commitment_scheme].

A vector commitment allows to commit to an ordered sequences of values in such a way that is later possible to open the commitment only with the reference to a specific position. [https://eprint.iacr.org/2011/495.pdf], (Catalano, Fiore).

In Verkle Tree 3,4, the commitment method is called vector commitment. In practice, it is used a more poweful, efficient and simplest method than a vector commitment, called polynomial commitment. Polynomial commitments let you hash and evaluate in any point the hashed polynomial (the polynomial can be found-defined with Lagrange interpolation). The two polynomial commitment schemes easiest to be used are: KZG and bulletprof-style commitments [https://vitalik.ca/general/2021/06/18/verkle.html] 3, [https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf] 4.

KZG commitments

The Kate commitment scheme is designed as a polynomial commitment, where it also allows a vector commitment. A vector commitment commits to a vector a0,...,an1a_0,...,a_{n-1} and lets you prove that you committed to aia_i for some ii. This could be reproduced using the Kate commitment scheme, which is a polynomial p(X)p(X) where for all ii, p(i)=aip(i)= a_i. This polynomial could be computed using Lagrange interpolation. [https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html].

Pedersen vector commitment

"It is shown how to distribute a secret to n persons such that each person can verify that he has received correct information about the secret without talking with other persons. Any kk of these persons can later find the secret 1<=k<=n1<=k<=n , whereas fewer than kk persons get no information about the secret." [https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf]. (Torben Pryds Pedersen)

Here you will find, that all verification of shares and the scheme are based in Lagrange Polynomial (section 4).